Product Code Database
In mathematics, the Bell triangle is a triangle of numbers analogous to Pascal's triangle, whose values count partitions of a set in which a given element is the largest singleton. It is named for its close connection to the ,According to , this name was suggested by Jeffrey Shallit, whose paper about the same triangle was later published as . Shallit in turn credits for the definition of the triangle, but Cohn et al. did not name the triangle. which may be found on both sides of the triangle, and which are in turn named after Eric Temple Bell. The Bell triangle has been discovered independently by multiple authors, beginning with and including also and , and for that reason has also been called Aitken's array or the Peirce triangle.
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
52 67 87 114 151 203
203 255 322 409 523 674 877
Thus, after the initial placement of the number 1 in the top row, it is the last position in its row and is copied to the leftmost position in the next row. The third value in the triangle, 2, is the sum of the two previous values above-left and left of it. As the last value in its row, the 2 is copied into the third row, and the process continues in the same way.
provide the following combinatorial interpretation of each value in the triangle. Following Sun and Wu, let ''An,k'' denote the value that is ''k'' positions from the left in the ''n''th row of the triangle, with the top of the triangle numbered as ''A''1,1. Then ''An,k'' counts the number of partitions of the set {1, 2, ..., ''n'' + 1} in which the element ''k'' + 1 is the only element of its set and each higher-numbered element is in a set of more than one element. That is, ''k'' + 1 must be the largest singleton of the partition.
For instance, the number 3 in the middle of the third row of the triangle would be labeled, in their notation, as A3,2, and counts the number of partitions of {1, 2, 3, 4} in which 3 is the largest singleton element. There are three such partitions:
In the same notation, augment the triangle with another diagonal to the left of its other values, of the numbers
1
0 1
1 1 2
1 2 3 5
4 5 7 10 15
11 15 20 27 37 52
41 52 67 87 114 151 203
162 203 255 322 409 523 674 877
This triangle may be constructed similarly to the original version of Bell's triangle, but with a different rule for starting each row: the leftmost value in each row is the difference of the rightmost and leftmost values of the previous row.
An alternative but more technical interpretation of the numbers in the same augmented triangle is given by .
In this way, as observed, this triangle can be interpreted as implementing the Gregory–Newton interpolation formula, which finds the coefficients of a polynomial from the sequence of its values at consecutive integers by using successive differences. This formula closely resembles a recurrence relation that can be used to define the Bell numbers.
The sums of each row of the triangle, 1, 3, 10, 37, ..., are the same sequence of first differences appearing in the second-from-right diagonal of the triangle.. The nth number in this sequence also counts the number of partitions of n elements into subsets, where one of the subsets is distinguished from the others; for instance, there are 10 ways of partitioning three items into subsets and then choosing one of the subsets..
|
|
